/*
 * Copyright (c) Huawei Technologies Co., Ltd. 2022-2022. All rights reserved.
 * Description: 性能评估器相关头文件
 * Author: sunzhepeng
 * Create: 2022-8-1
 */

#ifndef TOPO_DETECT_H
#define TOPO_DETECT_H

#include "graph_common_def.h"

namespace HcclEvaluator {

using PseudoQueue = struct PseudoQueue_t {
    std::vector<u32> data;
    u32 head;
    u32 tail;
    PseudoQueue_t(u32 size, u32 initVal) : data(size, initVal), head(0), tail(0)
    {
    }
};

class TopoDetect {
public:
    explicit TopoDetect() = default;
    virtual ~TopoDetect() = default;
    HcclResult Detect(AdjacencyMatrix<> &adjaMatrix, std::vector<AdjacencyMatrix<>> &topoMatrixes);
private:
    bool IsConnected(AdjacencyMatrix<> &adjaMatrix, u32 srcNode, u32 dstNode);
    HcclResult TestFullMesh(AdjacencyMatrix<> &topoMatrix, bool &isAllConnect, bool &isFullMesh);
    HcclResult GetConnectedSubGraph(AdjacencyMatrix<> &adjaMatrix, std::vector<AdjacencyMatrix<>> &topoMatrixes);
    HcclResult GetConnectedNode(AdjacencyMatrix<> &adjaMatrix, std::vector<std::vector<u32>> &ConnectedNodeVec);
    HcclResult AdjacencyMatrixBFS(AdjacencyMatrix<> &adjaMatrix, PseudoQueue &queue,
        std::vector<u32> &visited, u32 numSubGraph);
    HcclResult RemoveHamCycle(AdjacencyMatrix<> &adjaMatrix, std::vector<u32> &path);
    HcclResult FindHamCyclePos(AdjacencyMatrix<> &adjaMatrix, std::vector<u32> &path, u32 index, bool &found);
    HcclResult FindHamCycle(AdjacencyMatrix<> &adjaMatrix, std::vector<u32> &path, bool &found);
    HcclResult FindAllHamCycle(AdjacencyMatrix<> adjaMatrix, std::vector<std::vector<u32>> &paths);
};
} // namespace HcclEvaluator

#endif